package 剑指offer.数学;

/**
 * 手动实现 Math.pow
 *
 * 最简单的方式就是循环 n 次，把 base 乘 n 次。但是存在效率问题以及 n 的正负问题
 */
public class 第16题数值的整数次方 {

    /*
    以分析 2⁴ 为例
    2⁴ = 2 * 2 * 2 * 2 计算了 4 次
       = 2 * 2 * 4 计算了 3 次

    所以不需要遍历 n 次相乘，于是得出公式

         | a^(n/2) * a^(n/2)  n为偶数
    aⁿ =<
        |  a^(（n-1）/2) * a^(（n-1）/2) * a  n为奇数
     */
    public static double pow(double base, int n) {
        if (n == 0)
            return 1.0;
        if (n == 1)
            return base;
        boolean isNegative = false;
        if (n < 0) {
            n = -n;
            isNegative = true;
        }
        double res = pow(base, n >> 1);
        res *= res;   // ===> 这里模拟的是 a*a
        if ((n & 1) == 1) {
            // 说明 n 是奇数
            res *= base;
        }
        return isNegative ? 1/-res : res;
    }

    public static void main(String[] args) {
        System.out.println(pow(2, -3));
    }
}
